package org.chnxi.algorithm.floyd;

import java.util.Arrays;

/**
 * 佛罗伊德算法
 */
public class FloydAlgorithm {

    public static void main(String[] args) {
        final int N = 65535;
        char[] vertex = {'A','B','C','D','E','F','G'};
        int[][] matrix = new int[][]{
                {0, 5, 7, N, N, N, 2},
                {5, 0, N, 9, N, N, 3},
                {7, N, 0, N, 8, N ,N},
                {N, 9, N, 0, N, 4, N},
                {N, N, 8, N, 0, 5, 4},
                {N, N, N, 4, 5, 0, 6},
                {2, 3, N, N, 4, 6, 0}
        };

        Graph graph = new Graph(vertex.length , matrix , vertex);
        graph.print();
        System.out.println("===================");
        graph.floyd();
        graph.print();
    }

}

class Graph {

    private  char[] vertex;//存放节点数组

    private int[][] dis; //保存从各个顶点出发到其他顶点的距离，最后结果保留再该数组

    private  int[][] pre; //保存目标节点的前驱节点

    /**
     *
     * @param length 图中顶点的数量
     * @param matrix 邻接矩阵
     * @param vertix 顶点数组
     */
    public Graph(int length , int[][] matrix , char[] vertix){
        this.vertex = vertix;
        this.dis = matrix;
        this.pre = new int[length][length];

        //对pre进行初始化，存放的是前驱节点的下标
        for(int i = 0; i < length; i++){
            Arrays.fill(pre[i] , i);
        }
    }

    public void print(){
        System.out.println("----------dis----------");
        for (int i = 0 ; i < dis.length ; i++){
            for (int j = 0 ; j < dis.length ; j++){
                //System.out.printf("%11d" , dis[i][j]);
                System.out.print("<"+this.vertex[i] + "-" + (dis[i][j] == 65535 ? "N" : dis[i][j]) +"-"+this.vertex[j]+">" );
            }
            System.out.println();
        }

        System.out.println("----------pre----------");
        for (int i = 0 ; i < pre.length ; i++){
            for (int j = 0 ; j < pre.length ; j++){
                System.out.printf("%5d" , pre[i][j]);
            }
            System.out.println();
        }
    }

    /**
     * 算法实现
     */
    public void floyd(){
        int len = 0;
        //对中间顶点的遍历，k是中电顶点的下标
        for (int k=0; k<dis.length; k++){
            //从i顶点开始出发
            for(int i=0; i < dis.length; i++){
                // 到达j顶点，从i顶点出发，经过k顶点
                for (int j = 0; j < dis.length; j++){
                    //从i顶点出发，经过k中间顶点，到大j顶点的距离
                  len = dis[i][k] + dis[k][j];
                  if(len < dis[i][j]){ //如果len小于直连(dis[i][j])距离
                      dis[i][j] = len; //更新距离
                      pre[i][j] = pre[k][j]; //更新前驱顶点
                  }
                }

            }

        }
    }

}
